export class HashTable {
  storage = []
  count = 0
  limit = 7

  // 插入&修改操作
  put (key, value) {
    // 1.根据key获取对应的index
    let index = this.hashFunc(key, this.limit)

    // 2.根据index取出对应的bucket
    let bucket = this.storage[index]

    // 3.判断该bucket是否为null
    if (bucket == null) {
      bucket = []
      this.storage[index] = bucket
    }

    // 4.判断是否是修改数据
    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i]
      if (tuple[0] == key) {
        tuple[1] = value
        return
      }
    }

    // 5.进行添加操作
    bucket.push([key, value])
    this.count++

    // 6.判断是否需要扩容操作
    if (this.count > this.limit * 0.75) {
      let newPrime = this.getPrime(this.limit * 2)
      this.resize(newPrime)
    }
  }

  // 获取操作
  get (key) {
    // 1.根据key获取对应的index
    let index = this.hashFunc(key, this.limit)

    // 2.根据index获取对应的bucket
    let bucket = this.storage[index]

    // 3.判断bucket是否为null
    if (bucket == null) {
      return null
    }

    // 4.有bucket，那么就进行线性查找
    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i]
      if (tuple[0] == key) {
        return tuple[1]
      }
    }

    // 5.依旧没有找到，返回null
    return null
  }

  // 删除操作
  remove (key) {
    // 1.根据key获取对应的index
    let index = this.hashFunc(key, this.limit)

    // 2.根据index获取对应的bucket
    let bucket = this.storage[index]

    // 3.判断bucket是否为null
    if (bucket == null) return null

    // 4.有bucket，那么就进行线性查找，并且删除
    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i]
      if (tuple[0] == key) {
        bucket.splice(i, 1)
        this.count--

        // 缩小容量
        if (this.limit > 7 && this.count < this.limit * 0.25) {
          let newPrime = this.getPrime(Math.floor(this.limit / 2))
          this.resize(newPrime)
        }

        return tuple[1]
      }
    }

    // 5.依然没有找到，那么返回null
    return null
  }

  // 判断哈希表是否为空
  isEmpty () {
    return this.count == 0
  }

  // 获取哈希表中元素的个数
  size () {
    return this.count
  }

  // 哈希表扩容
  resize (newLimit) {
    // 1.保存旧的数组内容
    let oldStorage = this.storage

    // 2.重置所有的属性
    this.storage = []
    this.count = 0
    this.limit = newLimit

    // 3.遍历oldStorage中所有的bucket
    for (let i = 0; i < oldStorage.length; i++) {
      // 3.1.取出对应的bucket
      let bucket = oldStorage[i]

      // 3.2.判断bucket是否为null
      if (bucket == null) continue

      // 3.3.bucket中有数据，那么取出数据，重新插入
      for (let tuple of bucket) {
        this.put(tuple[0], tuple[1])
      }
    }
  }

  // 判断某个数字是否是质数
  isPrime (num) {
    // 1.获取num的平方根
    let temp = parseInt(Math.sqrt(num))

    // 2.循环判断
    for (let i = 2; i <= temp; i++) {
      if (num % i == 0) {
        return false
      }
    }

    return true
  }

  // 获取质数
  getPrime (num) {
    while (!this.isPrime(num)) {
      num++
    }
    return num
  }

  // 设计哈希函数
  // 1> 将字符串转成比较大的数字：hashCode
  // 2> 将大的数字hashCode压缩到数组范围（大小）之内
  hashFunc(str, size) {
    // 1.定义hashCode变量
    let hashCode = 0

    // 2.霍纳算法，来计算hashCode的值
    for (let i = 0; i < str.length; i++) {
      hashCode = 37 * hashCode + str.charCodeAt(i)
    }

    // 3.取余操作
    let index = hashCode % size

    return index
  }
}